Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (3,56)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 3 | |||
Set to 0 | 0 | Set to 1 | 1 | 56 | Quotient of 3/56 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 3/56 | 3 | Quotient of 56/3 | 18 |
0 - (18 x 1) | -18 | 1 - (18 x 0) | 1 | Remainder of 56/3 | 2 | Quotient of 3/2 | 1 |
1 - (1 x -18) | 19 | 0 - (1 x 1) | -1 | Remainder of 3/2 | 1 | Quotient of 2/1 | 2 |
-18 - (2 x 19) | -56 | 1 - (2 x -1) | 3 | Remainder of 2/1 | 0 | Quotient of 1/0 | 0 |
a = 19 and b = -1
ax + by = gcd(a,b)
3x + 56y = gcd(3